package com.leetcode.algorithm.y19.m04;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;

/**
 * leetcode-cn.com
 * BFS专题
 * (done)773. 滑动谜题
 * (done)529. 扫雷游戏
 * (done)994. 腐烂的橘子
 * @author: jie.deng
 * @time: 2019年4月2日 下午3:36:38
 */
public class MySolution0402 {
	
	/**
	 * 773. 滑动谜题
	 * 
	 * 在一个 2 x 3 的板上（board）有 5 块砖瓦，用数字 1~5 来表示, 以及一块空缺用 0 来表示.
	 * 
	 * 一次移动定义为选择 0 与一个相邻的数字（上下左右）进行交换.
	 * 
	 * 最终当板 board 的结果是 [[1,2,3],[4,5,0]] 谜板被解开。
	 * 
	 * 给出一个谜板的初始状态，返回最少可以通过多少次移动解开谜板，如果不能解开谜板，则返回 -1 。
	 * 
	 * 示例：
	 * 
	 * 输入：board = [[1,2,3],[4,0,5]]
	 * 输出：1
	 * 解释：交换 0 和 5 ，1 步完成
	 * 输入：board = [[1,2,3],[5,4,0]]
	 * 输出：-1
	 * 解释：没有办法完成谜板
	 * 输入：board = [[4,1,2],[5,0,3]]
	 * 输出：5
	 * 解释：
	 * 最少完成谜板的最少移动次数是 5 ，
	 * 一种移动路径:
	 * 尚未移动: [[4,1,2],[5,0,3]]
	 * 移动 1 次: [[4,1,2],[0,5,3]]
	 * 移动 2 次: [[0,1,2],[4,5,3]]
	 * 移动 3 次: [[1,0,2],[4,5,3]]
	 * 移动 4 次: [[1,2,0],[4,5,3]]
	 * 移动 5 次: [[1,2,3],[4,5,0]]
	 * 输入：board = [[3,2,4],[1,5,0]]
	 * 输出：14
	 * 提示：
	 * 
	 * board 是一个如上所述的 2 x 3 的数组.
	 * board[i][j] 是一个 [0, 1, 2, 3, 4, 5] 的排列.
	 * @param board
	 * @return
	 */
	public int slidingPuzzle(int[][] board) {
		StringBuilder sbSrcStr = new StringBuilder();
		for (int i = 0; i < board.length; i++) {
			for (int j = 0; j < board[i].length; j++) {
				sbSrcStr.append(board[i][j]);
			}
		}
		String srcStr = sbSrcStr.toString();
		String targetStr = "123450";
		if (targetStr.equals(srcStr)) {
			return 0;
		}
		Set<String> visitedSet = new HashSet<String>(6 * 5 * 4 * 3 * 2 * 1);
		Queue<String> queue = new LinkedList<String>();
		int level = 1;
		queue.offer(srcStr);
		visitedSet.add(srcStr);
		while (!queue.isEmpty()) {
			int levelSize = queue.size();
			for (int i = 0; i < levelSize; i++) {
				String curStr = queue.poll();
				StringBuilder sbStr = null;
				String str = null;
				int idx = curStr.indexOf('0');
				// 左
				if (idx != 0 && idx != 3) {
					sbStr = new StringBuilder(curStr);
					sbStr.setCharAt(idx, curStr.charAt(idx - 1));
					sbStr.setCharAt(idx - 1, '0');
					str = sbStr.toString();
					if (!visitedSet.contains(str)) {
						if (targetStr.equals(str)) {
							return level;
						}
						queue.offer(str);
						visitedSet.add(str);
					}
				}
				// 右
				if (idx != 2 && idx != 5) {
					sbStr = new StringBuilder(curStr);
					sbStr.setCharAt(idx, curStr.charAt(idx + 1));
					sbStr.setCharAt(idx + 1, '0');
					str = sbStr.toString();
					if (!visitedSet.contains(str)) {
						if (targetStr.equals(str)) {
							return level;
						}
						queue.offer(str);
						visitedSet.add(str);
					}
				}
				// 上
				if (idx >= 3) {
					sbStr = new StringBuilder(curStr);
					sbStr.setCharAt(idx, curStr.charAt(idx - 3));
					sbStr.setCharAt(idx - 3, '0');
					str = sbStr.toString();
					if (!visitedSet.contains(str)) {
						if (targetStr.equals(str)) {
							return level;
						}
						queue.offer(str);
						visitedSet.add(str);
					}
				}
				// 下
				if (idx < 3) {
					sbStr = new StringBuilder(curStr);
					sbStr.setCharAt(idx, curStr.charAt(idx + 3));
					sbStr.setCharAt(idx + 3, '0');
					str = sbStr.toString();
					if (!visitedSet.contains(str)) {
						if (targetStr.equals(str)) {
							return level;
						}
						queue.offer(str);
						visitedSet.add(str);
					}
				}
			}
			level++;
		}

		return -1;
	}
    
    /**
     * 529. 扫雷游戏
     * 
	 * 让我们一起来玩扫雷游戏！
	 * 
	 * 给定一个代表游戏板的二维字符矩阵。 'M' 代表一个未挖出的地雷，'E' 代表一个未挖出的空方块，'B' 代表没有相邻（上，下，左，右，和所有4个对角线）地雷的已挖出的空白方块，数字（'1' 到 '8'）表示有多少地雷与这块已挖出的方块相邻，'X' 则表示一个已挖出的地雷。
	 * 
	 * 现在给出在所有未挖出的方块中（'M'或者'E'）的下一个点击位置（行和列索引），根据以下规则，返回相应位置被点击后对应的面板：
	 * 
	 * 如果一个地雷（'M'）被挖出，游戏就结束了- 把它改为 'X'。
	 * 如果一个没有相邻地雷的空方块（'E'）被挖出，修改它为（'B'），并且所有和其相邻的方块都应该被递归地揭露。
	 * 如果一个至少与一个地雷相邻的空方块（'E'）被挖出，修改它为数字（'1'到'8'），表示相邻地雷的数量。
	 * 如果在此次点击中，若无更多方块可被揭露，则返回面板。
	 *  
	 * 
	 * 示例 1：
	 * 
	 * 输入: 
	 * 
	 * [['E', 'E', 'E', 'E', 'E'],
	 *  ['E', 'E', 'M', 'E', 'E'],
	 *  ['E', 'E', 'E', 'E', 'E'],
	 *  ['E', 'E', 'E', 'E', 'E']]
	 * 
	 * Click : [3,0]
	 * 
	 * 输出: 
	 * 
	 * [['B', '1', 'E', '1', 'B'],
	 *  ['B', '1', 'M', '1', 'B'],
	 *  ['B', '1', '1', '1', 'B'],
	 *  ['B', 'B', 'B', 'B', 'B']]
	 * 
	 * 解释:
	 * 
	 * 示例 2：
	 * 
	 * 输入: 
	 * 
	 * [['B', '1', 'E', '1', 'B'],
	 *  ['B', '1', 'M', '1', 'B'],
	 *  ['B', '1', '1', '1', 'B'],
	 *  ['B', 'B', 'B', 'B', 'B']]
	 * 
	 * Click : [1,2]
	 * 
	 * 输出: 
	 * 
	 * [['B', '1', 'E', '1', 'B'],
	 *  ['B', '1', 'X', '1', 'B'],
	 *  ['B', '1', '1', '1', 'B'],
	 *  ['B', 'B', 'B', 'B', 'B']]
	 * 
	 * 解释:
	 * 
	 *  
	 * 
	 * 注意：
	 * 
	 * 输入矩阵的宽和高的范围为 [1,50]。
	 * 点击的位置只能是未被挖出的方块 ('M' 或者 'E')，这也意味着面板至少包含一个可点击的方块。
	 * 输入面板不会是游戏结束的状态（即有地雷已被挖出）。
	 * 简单起见，未提及的规则在这个问题中可被忽略。例如，当游戏结束时你不需要挖出所有地雷，考虑所有你可能赢得游戏或标记方块的情况。
     * @param board
     * @param click
     * @return
     */
	public char[][] updateBoard(char[][] board, int[] click) {
		char clickCh = board[click[0]][click[1]];
		if (clickCh == 'M') {
			board[click[0]][click[1]] = 'X';
			return board;
		}
		int rows = board.length;
		int cols = board[0].length;
		boolean[][] visited = new boolean[rows][cols];
		Queue<Integer[]> queue = new LinkedList<Integer[]>();
		queue.offer(new Integer[] { click[0], click[1] });
		while (!queue.isEmpty()) {
			Integer[] pos = queue.poll();
			if (visited[pos[0]][pos[1]]) {
				continue;
			}
			int mCnt = 0;
			List<Integer[]> posList = new ArrayList<Integer[]>(8);
			int[][] neignbourPosArr = new int[][] { 
				new int[] { pos[0] - 1, pos[1] - 1 }, new int[] { pos[0] - 1, pos[1] }, new int[] { pos[0] - 1, pos[1] + 1 },
				new int[] { pos[0], 	pos[1] - 1 }, 									new int[] { pos[0], 	pos[1] + 1 },
				new int[] { pos[0] + 1, pos[1] - 1 }, new int[] { pos[0] + 1, pos[1] }, new int[] { pos[0] + 1, pos[1] + 1 } };
			for (int i = 0; i < 8; i++) {
				int r = neignbourPosArr[i][0];
				int c = neignbourPosArr[i][1];
				if (r >= 0 && r < rows && c >= 0 && c < cols) {
					switch (board[r][c]) {
					case 'M':
						mCnt++;
						break;
					case 'E':
						posList.add(new Integer[] { r, c });
						break;
					default:
						break;
					}
				}
			}

			if (mCnt > 0) {
				board[pos[0]][pos[1]] = (char) ('0' + mCnt);
			} else {
				board[pos[0]][pos[1]] = 'B';
				for (int i = 0; i < posList.size(); i++) {
					queue.offer(posList.get(i));
				}
			}
			visited[pos[0]][pos[1]] = true;
		}
		return board;
	}

	/**
     * 994. 腐烂的橘子
     * 
	 * 在给定的网格中，每个单元格可以有以下三个值之一：
	 * 
	 * 值 0 代表空单元格；
	 * 值 1 代表新鲜橘子；
	 * 值 2 代表腐烂的橘子。
	 * 每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜橘子都会腐烂。
	 * 
	 * 返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1。
	 * 
	 *  
	 * 
	 * 示例 1：
	 * 
	 * 
	 * 
	 * 输入：[[2,1,1],[1,1,0],[0,1,1]]
	 * 输出：4
	 * 示例 2：
	 * 
	 * 输入：[[2,1,1],[0,1,1],[1,0,1]]
	 * 输出：-1
	 * 解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个正向上。
	 * 示例 3：
	 * 
	 * 输入：[[0,2]]
	 * 输出：0
	 * 解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。
	 *  
	 * 
	 * 提示：
	 * 
	 * 1 <= grid.length <= 10
	 * 1 <= grid[0].length <= 10
	 * grid[i][j] 仅为 0、1 或 2
     */
	public int orangesRotting(int[][] grid) {
		int rows = grid.length;
		int cols = grid[0].length;
		int val1Cnt = 0;
		Queue<Integer[]> queue = new LinkedList<Integer[]>();
		boolean[][] visited = new boolean[rows][cols]; // 避免加入重复的数据到queue
		for (int i = 0; i < rows; i++) {
			for (int j = 0; j < cols; j++) {
				switch (grid[i][j]) {
				case 1:
					val1Cnt++;
					break;
				case 2:
					queue.offer(new Integer[] { i, j });
					visited[i][j] = true;
					break;
				default:
					break;
				}
			}
		}
		if (val1Cnt == 0) {
			return 0;
		}
		int levelSize = queue.size();
		if (levelSize == 0) {
			return -1;
		}
		int level = 1;
		while (!queue.isEmpty()) {
			for (int k = 0; k < levelSize; k++) {
				Integer[] pos = queue.poll();
				int[][] neignbourPosArr = new int[][] { new int[] { pos[0] - 1, pos[1] },
						new int[] { pos[0], pos[1] - 1 }, new int[] { pos[0], pos[1] + 1 },
						new int[] { pos[0] + 1, pos[1] } };
				for (int i = 0; i < 4; i++) {
					int r = neignbourPosArr[i][0];
					int c = neignbourPosArr[i][1];
					if (r >= 0 && r < rows && c >= 0 && c < cols) {
						if (grid[r][c] == 1) {
							val1Cnt--;
							if (val1Cnt == 0) {
								return level;
							}
							grid[r][c] = 2;
							if (!visited[r][c]) {
								queue.offer(new Integer[] { r, c });
								visited[r][c] = true;
							}
						}
					}
				}
			}
			level++;
			levelSize = queue.size();
		}
		return -1;
	}
    
}
